1. Field of the Invention
The present invention relates generally to computer graphics and more particularly, to an improved process, apparatus, and article of manufacture for visible surface determination.
2. Description of Related Art
One or more three-dimensional object(s), together with their relative positions and orientations in three-dimensional coordinate space constitutes a three-dimensional scene. Generally, a three-dimensional object can be defined by a number of surfaces. A three-dimensional graphics renderer is a device, which translates a description of a three-dimensional scene containing a set of three-dimensional objects, into a two-dimensional image for display on display device such as a computer screen or other two-dimensional display medium. The graphics renderer can be implemented in dedicated hardware, software running on general purpose CPU, or a combination thereof.
As shown by the exemplary graphics rendering pipeline in FIG. 1A, rendering is a multi-step process. Bearing in mind that the particular order described below is not limiting in any sense, one way of ordering the steps follows:                1. Define a three-dimensional scene having three-dimensional objects by local or generalized coordinates;        2. Perform several transformations of local coordinates to world coordinates to eye or view coordinates;        3. Perform a perspective or parallel projection;        4. Perform back-face culling;        5. Determine visible surfaces;        6. Rasterize and write to a frame buffer; and        7. Display or store the generated image of the three-dimensional scene.        
Every two-dimensional projection of a three-dimensional scene is generated assuming a particular location of an observer. A two-dimensional scene is then created from the observer's frame of reference, generally employing a view plane. The forgoing process is simplified if, for example, a coordinate system is adopted in which the observer is located at the origin, looking down the z-axis in the positive z direction. This type of coordinate system is called an eye or view coordinate system. Three-dimensional scenes are frequently described in generalized or local coordinates, which may have as their origin a location other than that of the observer. Thus, all objects intended for display in a two-dimensional system created from the observer's frame of reference must have their local or generalized coordinates expressed in eye coordinates. Generalized coordinates can be mapped to eye coordinates through conventional transformation techniques.
Reference is now made to FIG. 1, which is an illustration of a view volume 10, defined by a frustum (i.e., a truncated pyramid) and including a front and back clipping planes and a view plane. A view volume bounds a region in coordinate space that will be clipped and projected onto a view plane. While a view volume may have infinite extent, in practice, a view volume is delimited by using a front clipping plane abcd (12) and the back clipping plane a1b1c1d1 (14). The projection of a three-dimensional object is defined by straight projection rays 16, emanating from the origin of an eye coordinate system, passing through each point of the object and intersecting a view plane a2b2c2d2 (18) to form the projection. For an arbitrary point of a three-dimensional object, a vector directed from this point to the origin of eye coordinate system defines the direction of projection. The view plane can be located anywhere with respect to the front and back clipping planes.
A perspective transformation transforms three-dimensional objects from an eye coordinate system to a device coordinate system. After this transformation, the parallel projection of the transformed object is the same as the perspective projection of the original object. Reference is now made to FIG. 2A and FIG. 2B, which are illustrations of a cube before and after perspective transformation.
Perspective transformed coordinates are useful because they not only reveal how an object on a view plane appears to the observer, but also how distant the object is from the observer in the z direction. The distance of an object from the observer in the z direction, determines which objects or surfaces appear “in front” and which appear “behind” to the observer. Therefore, the z coordinate is an important item used for determining hidden objects or surfaces or hidden portions thereof.
Every transformed three-dimensional geometric entity, has a corresponding two-dimensional projection, which is derived from the three-dimensional geometric entity by simply eliminating the z coordinate for each point and retaining the x and y coordinates.
Reference is now made to FIG. 3, which is an illustration of an object 20 defined by three-dimensional eye coordinates. Object 20 consists of two faces, a front face 22A and a back face 22B. The front face 22A is visible to the observer 24 and is subject to further processing. The back face 22B is oriented away from the observer, i.e., hidden from view, and can be quickly identified and removed based solely on it's orientation. The conventional back-face culling technique is a pre-processing step that can quickly identify and remove an object's back faces without regard to other surfaces and objects in the scene. If the surface of the three-dimensional object 20 is transparent then both surfaces 22A and 22B are visible to observer 24. In this case, a back face surface may be considered a front face and therefore, would not be removed during the back face culling routine.
In determining visible surfaces, a renderer has to remove hidden surfaces from the rendered scene. There exist many conventional techniques for removing hidden surfaces, including, z-buffer, scan-line, ray tracing, etc. These and other well-known techniques are disclosed in the publication “Introduction to Computer Graphics” by James D. Foley and others, published by Addison Wesley Publishing Co., and incorporated herein by reference. A main drawback of all the forgoing methods is the computational complexity. The number of required calculations in all the existing methods, such as z-buffer, scan-line, ray tracing, etc., is proportional to the total surface of objects of the scene.
U.S. Pat. No. 3,602,702 discloses an area-subdivision method of generating two-dimensional images of three-dimensional objects. In this method, the total area of a view plane is progressively divided into smaller subdivisions. As the subdivisions become smaller fewer polygons overlap each subdivision, and ultimately it is possible to decide which polygons are visible in the subdivisions. In order to determine visible polygons over a subdivision all the polygons, which are projected at least partially onto the subdivision must be checked. While this method can reduce the number of required calculations to a number which is smaller than that of other previously mentioned methods, nevertheless, the number of polygons, which must be checked is very high. Thus, a solution is needed which overcomes the deficiencies in the prior art.